/*
 * @Descripttion: 
 * @version: 
 * @Author: xuyouchang
 * @Date: 2022-01-17 20:11:14
 * @LastEditors: xuyouchang
 * @LastEditTime: 2022-01-17 21:46:29
 */
package com.sure0000.dataStructure;

public class BinaryNode {
    private Integer value;
    private BinaryNode leftNode;
    private BinaryNode rightNode;

    public BinaryNode getLeftNode() {
        return leftNode;
    }

    public BinaryNode getRightNode() {
        return rightNode;
    }

    public Integer getValue() {
        return value;
    }

    public void setValue(Integer value) {
        this.value = value;
    }

    // 添加树节点
    public void addNode(Integer value) {
        if(value == null) {
            this.value = value;
        }else if(value < this.value) {
            leftNode.addNode(value);
        }else{
            rightNode.addNode(value);
        }
    }

    // 查找
    public static boolean searchNode(BinaryNode binaryNode, Integer value) {
        if(binaryNode.getValue() == value) {
            return true;
        }else if(value < binaryNode.getValue()) {
            return searchNode(binaryNode.getLeftNode(), value);
        }else{
            return searchNode(binaryNode.getRightNode(), value);
        }
    }

    // 获取二叉树最大节点
    public static BinaryNode maxNode(BinaryNode binaryNode) {
        if(binaryNode.getRightNode() == null) {
            return binaryNode;
        }
        return maxNode(binaryNode.getRightNode());
    }

    // 获取二叉树最小节点
    public static BinaryNode minNode(BinaryNode binaryNode) {
        if(binaryNode.getLeftNode() == null) {
            return binaryNode;
        }
        return minNode(binaryNode.getLeftNode());
    }

    // 删除左子树最大节点
    public static void removeNode(BinaryNode binaryNode) {
        if(binaryNode.getRightNode() == null) {
            binaryNode = null;
            return;
        }
        removeNode(binaryNode.getRightNode());
    }

    public static BinaryNode deleteNode(BinaryNode binaryNode, Integer value) {
        if(binaryNode.getValue() == value) {
            // 没有左右子树
            if(binaryNode.getLeftNode() == null && binaryNode.getRightNode() == null) {
                binaryNode = null;
            }

            // 只有左子树
            if(binaryNode.getLeftNode() != null && binaryNode.rightNode == null) {
                binaryNode = binaryNode.getLeftNode();
            }

            // 只有右子树
            if(binaryNode.getLeftNode() == null && binaryNode.getRightNode() != null) {
                binaryNode = binaryNode.getRightNode();
            }

            // 左右子树都在
            // 取左子树最大值或右子树最小值替换该节点
            // 删除替换节点
            if(binaryNode.getLeftNode() != null && binaryNode.getRightNode() != null) {
                binaryNode.setValue(maxNode(binaryNode.getLeftNode()).getValue());
                removeNode(binaryNode);
            }
            return binaryNode;
        }else if(value < binaryNode.getValue()) {
            return deleteNode(binaryNode.getLeftNode(), value);
        }else{
            return deleteNode(binaryNode.getRightNode(), value);
        }
    }
}
